package com.lsa.letcode.the91.decodeWays;

import java.util.Arrays;

public class Solution {
	private static final boolean DEBUG_PRINT = false;
	
    public int numDecodings(String s) {
    	if (s.length() < 1) {
    		return 0; 
    	}
    	int count = 0;
    	
    	Combination c = new Combination(s.length() - 1);
        do{
        	if (DEBUG_PRINT) {
        		print(s, c);
        	}
        	if (isMessage(s, c)) {
        		count++;
        		System.out.println(count);
        		if (DEBUG_PRINT) {
        			System.out.println(" +");
        		}
        	}
        	else {
        		if (DEBUG_PRINT) {
        			System.out.println(" -");
        		}
        	}
        }
        while(c.next());
        
    	return count;
    }
    
    static void print(String s, Combination c) {
    	int[] bits = c.bits;
    	int prevBracketIdx = -1;
    	for (int i = 0; i < bits.length; i++) {
			if (bits[i] != 0) {
				print(s, prevBracketIdx, i);
				prevBracketIdx = i;
			}
		}
    	
    	print(s, prevBracketIdx, s.length() - 1);
    }

	private static void print(String s, int prevBracketIdx, int i) {
		String sub = s.substring(prevBracketIdx + 1, i + 1);
		System.out.print(sub+")(");
	}
    
    static boolean isMessage(String s, Combination c) {
    	int prevBracketIdx = -1;
    	int[] bits = c.bits;
    	
		for (int i = 0; i < bits.length; i++) {
			if (bits[i] != 0) {
				if (!extractSubAndCheck(s, prevBracketIdx, i)){
					return false;
				}
				prevBracketIdx = i;
			}
		}
		
		if (!extractSubAndCheck(s, prevBracketIdx, s.length() - 1)) {
			return false;
		}
		
    	return true;
    }

	private static boolean extractSubAndCheck(String s, int prevBracketIdx,
			int i) {
		String sub = s.substring(prevBracketIdx + 1, i + 1);
		
		int num = 0;
		for (int j = 0; j < sub.length(); j++) {
			char c = sub.charAt(j);
			if (c < '0' || c > '9') {
				return false;
			}
			num = num * 10 + (c - '0');
			if (1 > num || 26 < num) {
				return false;
			}
		}
		
		if (num < 10 && sub.length() != 1) {
			return false;
		}
		if (num > 9 && sub.length() != 2) {
			return false;
		}
		return true;
	}
	
	static class Combination {
    	int[] bits;
    	private static int ONE = 0;
    	private static int ZERO = 1;
    	
    	
    	Combination(int len) {
    		bits = new int[len];
    		Arrays.fill(bits, ZERO);
    	}
    	
    	private int bit(int i) {
    		if (i > -1 &&  i < bits.length) {
    			return bits[i];
    		}
    		else if (i == -1){
    			return ZERO;
    		}
    		else {
    			return ONE;
    		}
    	}
    	
    	boolean next(){
    		if (bits.length == 0) {
    			return false;
    		}
    		boolean hasNext = false; 
    		for (int i = bits.length - 1; i > -1; i--) {
    			if (bit(i - 1) == ZERO && bit(i) == ZERO && bit(i + 1) == ONE) {
					bits[i] = ONE;
					for (int j = i + 1; j < bits.length; j++) {
						bits[j] = ZERO;
					}
					hasNext = true;
					break;
				}
    		}
    		
    		return hasNext;
    	}
    }
    
//    static class Combination {
//    	int[] bits;
//    	
//    	Combination(int len) {
//    		bits = new int[len];
//    	}
//    	
//    	void flip(int i, int bit) {
//    		bits[i] = bit;
//    	}
//    	
//    	boolean next(){
//    		if (bits.length == 0) {
//    			return false;
//    		}
//    		int carry = 0;
//        	for (int i = bits.length - 1; i > -1; i--) {
//    			int d = bits[i] + carry + (i == bits.length - 1? 1 : 0);
//    			carry = d / 2;
//    			d = d % 2;
//    			flip(i, d);
//    		}
//    		return carry == 0;
//    	}
//    }
}

/*
  1 2 3
 () ( )
 
  1 2 3
 (  )()
 
  1 2 3
 ()()()

*/